/*
 * @Author: szx
 * @Date: 2021-11-11 13:22:18
 * @LastEditTime: 2021-11-11 14:01:31
 * @Description:
 * @FilePath: \leetcode\900-999\986\986.cpp
 */
#include <iostream>
#include <vector>
using namespace std;
class Solution {
   public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList,
                                             vector<vector<int>>& secondList) {
        int m = firstList.size(), n = secondList.size();

        vector<vector<int>> res;
        int num = 0;
        for (int i = 0; i < m; i++) {
            for (int j = num; j < n; j++) {
                // cout<<i<<" "<<j<<" "<<num<<endl;
                if (secondList[j][0] > firstList[i][1]) {
                    num = j - 1 > 0 ? j - 1 : 0;
                    break;
                }
                if (firstList[i][0] > secondList[j][1]) {
                    num = j + 1;
                    continue;
                }
                res.push_back({max(firstList[i][0], secondList[j][0]),
                               min(firstList[i][1], secondList[j][1])});
            }
        }
        return res;
    }
};

class Solution {
   public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList,
                                             vector<vector<int>>& secondList) {
        int m = firstList.size(), n = secondList.size();

        vector<vector<int>> res;
        int i = 0, j = 0;
        while (i < m && j < n) {
            int lo = max(firstList[i][0], secondList[j][0]);
            int hi = min(firstList[i][1], secondList[j][1]);
            if (lo <= hi) {
                res.push_back({lo, hi});
            }
            if (firstList[i][1] < secondList[j][1]) {
                i++;
            } else {
                j++;
            }
        }
        return res;
    }
};